package 二叉树;

import Utils.TreeNode;

/**
 * @author TTDB
 * @create 2025/9/18
 */
public class lowestCommonAncestor {
     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
         //二叉树的公共祖先，为null,就是null,出现了p,q那就是p,q之中的这一个
        if (root == null || root == p || root == q) {
            return root;
        }
        //都没出现就递归左右去找
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        //找完谁是null就返回另一个
        if (left == null) {
            return right;
        }
        if (right == null) {
            return left;
        }
        return root;
     }
}
